/**
 * 描述：链表为底层的Map
 *
 * @author 王博
 * @version 1.0
 * create 2018-10-23-23:00
 */
public class LinkedListMap<K,V> implements Map<K,V>{
    /**
     * 在LinkedList这个类中设置一个
     * 私有内部类。只有在这个类的内部
     * 才可以访问的到这个类。
     */
    private class Node{
        public K key;
        public V value;
        public Node next;


        /**
         * 构造函数
         * @param key 传入的key
         * @param value 传入的value
         * @param next 传入的下一个节点
         */
        public Node(K key,V value, Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }

        /**
         * 这个构造函数只传入e
         * @param key 传入的key
         */
        public Node(K key){
            this(key,null,null);
        }

        /**
         * 这个构造函数什么也不传入
         */
        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString(){
            return key.toString () + ":" + value.toString ();
        }
    }

    private Node dummyHead;
    private int size;

    /**
     * 链表实现的Map的构造函数
     */
    public LinkedListMap(){
        dummyHead = new Node ();
        size = 0 ;
    }

    @Override
    public int getSize( ) {
        return size;
    }

    @Override
    public boolean isEmpty( ) {
        return size == 0;
    }

    /**
     * 辅助的函数，传入节点key，返回节点所对应的引用
     * @param key 传入节点的key值
     * @return key节点所对应的引用
     */
    private Node getNode(K key){
        Node cur = dummyHead.next;//指向头节点
        while (cur!=null){
            if(cur.key.equals (key)){//注意用equals
                return cur;
            }else {
                cur = cur.next;
            }
        }
        return null;
    }

    @Override
    public void add(K key , V value) {
        Node node = getNode (key);
        if(node == null){
            dummyHead.next = new Node(key,value,dummyHead.next);//在头部添加一个元素
            size++;
        }else {
            //已经存在。所以更新一下。（具体设计模式自己考虑，根据需求来）
            node.value = value;
        }
    }

    @Override
    public V remove(K key) {
        Node prev = dummyHead;

        while(prev.next!= null)
        {
            if(prev.next.value.equals (key)){
                break;
            }else
                prev = prev.next;
        }

        if(prev.next!=null)
        {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
            return delNode.value;
        }
        return null;
    }

    @Override
    public void set(K key , V newValue) {
        Node node = getNode (key);
        if(node==null){
            throw new IllegalArgumentException (key + "dones`t exist!");}
        else{
            node.value = newValue;
        }
    }

    @Override
    public boolean contains(K key) {
        return getNode (key)!=null;
    }

    @Override
    public V get(K key) {
        Node node = getNode (key);

        return node ==null?null:node.value;//如果节点为空返回空，否则返回值
    }


}
